#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1996. 游戏中弱角色的数量
// 【难度】中等
// 【提交】2025 9 18 https://leetcode.cn/problems/the-number-of-weak-characters-in-the-game/submissions/663847146/
// 【标签】排序；贪心算法
class Solution_LC1996 {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        sort(properties.begin(), properties.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        
        int max = 0;
        int count = 0;
        
        for (auto& p : properties) {
            if (p[1] < max) {
                count++;
            } else {
                max = p[1];
            }
        }
        return count;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个二维数组 properties，其中 properties[i] = [attack_i, defense_i] 表示游戏中第 i 个角色的攻击和防御能力。
 * 如果一个角色的攻击和防御能力都严格低于另一个角色，则该角色被称为弱角色。返回弱角色的数量。
 * 模型：排序 + 贪心算法，通过巧妙的排序方式简化问题。
 * 
 * 二、标准解法状态设计
 * 将角色按照攻击力降序排序，攻击力相同时按照防御力升序排序。
 * 然后遍历排序后的角色，维护一个当前最大防御力。对于每个角色，如果其防御力小于当前最大防御力，
 * 则说明存在一个攻击力更高（由于排序）且防御力更高的角色，因此当前角色是弱角色。
 * 
 * 三、你的实现思路
 * 使用自定义排序和一次遍历的方法，高效地统计弱角色数量。
 * 
 * 四、逐行注释（带细节提醒）
 * sort(properties.begin(), properties.end(), [](const vector<int>& a, const vector<int>& b) {
 *     return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0]; // 攻击力降序，防御力升序
 * });
 * int maxDefense = 0; // 初始化最大防御力
 * int count = 0;      // 初始化弱角色计数器
 * for (auto& p : properties) { // 遍历排序后的角色
 *     if (p[1] < maxDefense) { // 如果当前防御力小于最大防御力
 *         count++;     // 增加弱角色计数
 *     } else {
 *         maxDefense = p[1]; // 更新最大防御力
 *     }
 * }
 * 
 * 五、正确性证明
 * 排序后，攻击力高的角色在前。对于攻击力相同的角色，防御力低的在前。
 * 这样，当我们遍历时，对于每个角色，之前遇到的角色要么攻击力更高，要么攻击力相同但防御力更高。
 * 因此，如果当前角色的防御力小于之前遇到的最大防御力，则必然存在一个攻击力更高或相等的角色，
 * 且该角色的防御力更高，因此当前角色是弱角色。
 * 
 * 六、复杂度
 * 时间：O(n log n)，主要由排序操作决定。
 * 空间：O(log n)，排序所需的栈空间（快速排序）。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法思路巧妙，通过排序将二维问题转化为一维问题；
 *   - 代码简洁，实现高效；
 *   - 只需一次遍历，时间复杂度主要由排序决定。
 * 缺点：
 *   - 排序操作可能对大数据集有一定开销；
 *   - 排序策略的理解需要一定的思维转换。
 * 
 * 八、改进建议
 * 1. 可以添加提前判断：if (properties.empty()) return 0;
 * 2. 使用更明确的变量名（如 maxDefense）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么排序策略如此设计。
 * 
 * 九、一句话总结
 * 通过巧妙的排序策略将二维问题转化为一维问题，你的实现准确且高效，展现了解决复杂问题的简化思维能力。
 */